{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Recolors to Get K Consecutive Black Blocks"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumRecolors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #得到 K 个黑块的最少涂色次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个长度为 <code>n</code>&nbsp;下标从 <strong>0</strong>&nbsp;开始的字符串&nbsp;<code>blocks</code>&nbsp;，<code>blocks[i]</code>&nbsp;要么是&nbsp;<code>'W'</code>&nbsp;要么是&nbsp;<code>'B'</code>&nbsp;，表示第&nbsp;<code>i</code>&nbsp;块的颜色。字符&nbsp;<code>'W'</code> 和&nbsp;<code>'B'</code>&nbsp;分别表示白色和黑色。</p>\n",
    "\n",
    "<p>给你一个整数&nbsp;<code>k</code>&nbsp;，表示想要&nbsp;<strong>连续</strong>&nbsp;黑色块的数目。</p>\n",
    "\n",
    "<p>每一次操作中，你可以选择一个白色块将它 <strong>涂成</strong>&nbsp;黑色块。</p>\n",
    "\n",
    "<p>请你返回至少出现 <strong>一次</strong>&nbsp;连续 <code>k</code>&nbsp;个黑色块的 <strong>最少</strong>&nbsp;操作次数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>blocks = \"WBBWWBBWBW\", k = 7\n",
    "<b>输出：</b>3\n",
    "<strong>解释：</strong>\n",
    "一种得到 7 个连续黑色块的方法是把第 0 ，3 和 4 个块涂成黑色。\n",
    "得到 blocks = \"BBBBBBBWBW\" 。\n",
    "可以证明无法用少于 3 次操作得到 7 个连续的黑块。\n",
    "所以我们返回 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>blocks = \"WBWBBBW\", k = 2\n",
    "<b>输出：</b>0\n",
    "<strong>解释：</strong>\n",
    "不需要任何操作，因为已经有 2 个连续的黑块。\n",
    "所以我们返回 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><b>提示：</b></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == blocks.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 100</code></li>\n",
    "\t<li><code>blocks[i]</code>&nbsp;要么是&nbsp;<code>'W'</code>&nbsp;，要么是&nbsp;<code>'B'</code> 。</li>\n",
    "\t<li><code>1 &lt;= k &lt;= n</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-recolors-to-get-k-consecutive-black-blocks](https://leetcode.cn/problems/minimum-recolors-to-get-k-consecutive-black-blocks/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-recolors-to-get-k-consecutive-black-blocks](https://leetcode.cn/problems/minimum-recolors-to-get-k-consecutive-black-blocks/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"WBBWWBBWBW\"\\n7', '\"WBWBBBW\"\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRecolors(self, blocks: str, k: int) -> int:\n",
    "        nWhites: int = sum(1 if blocks[i] == \"W\" else 0 for i in range(k))\n",
    "        minOps: int = nWhites\n",
    "\n",
    "        for i in range(1, len(blocks) - k + 1):\n",
    "            if blocks[i - 1] != blocks[i + k - 1]:\n",
    "                nWhites += 1 if blocks[i + k - 1] == \"W\" else -1\n",
    "            minOps = min(minOps, nWhites)\n",
    "\n",
    "        return minOps"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRecolors(self, blocks: str, k: int) -> int:\n",
    "        if len(blocks)<k:\n",
    "            return False\n",
    "        res = inf\n",
    "        for i in range(len(blocks)-k+1):\n",
    "            a = Counter(blocks[i:i+k])\n",
    "            res = min(res,a['W'])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRecolors(self, blocks: str, k: int) -> int:\n",
    "        L = [blocks[i:i+k].count('W') for i in range(len(blocks)-k+1)]\n",
    "        return min(L)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRecolors(self, blocks: str, k: int) -> int:\n",
    "        from collections import Counter\n",
    "        res = k\n",
    "        blocks_len = len(blocks)\n",
    "        for i in range(blocks_len - k + 1):\n",
    "            temp_block = blocks[i:i + k]\n",
    "            # print(temp_block)\n",
    "            temp_dict = Counter(temp_block)\n",
    "            cur_step = k - temp_dict.get('B', 0)\n",
    "            # print(cur_step)\n",
    "            res = min(cur_step, res)\n",
    "            if res == 0:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRecolors(self, blocks: str, k: int) -> int:\n",
    "        blocks = list(blocks)\n",
    "        # print(blocks)\n",
    "        r = 0\n",
    "        left = 0\n",
    "        right = k-1\n",
    "\n",
    "        for idx in range(k):\n",
    "            block = blocks[idx]\n",
    "            if block == \"W\":\n",
    "                r += 1\n",
    "        \n",
    "        f = r\n",
    "        n = len(blocks)\n",
    "\n",
    "        while right < n-1:\n",
    "            print(r, f)\n",
    "            right = right+1\n",
    "            if (blocks[left] == \"W\" and blocks[right] == \"W\") or (blocks[left] == \"B\" and blocks[right] == \"B\"):\n",
    "                left += 1\n",
    "                continue\n",
    "            elif (blocks[left] == \"W\" and blocks[right] == \"B\"):\n",
    "                r -= 1\n",
    "                f = min(r, f)\n",
    "            else:\n",
    "                r += 1\n",
    "                f = min(r, f)\n",
    "            left += 1\n",
    "        return f\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRecolors(self, blocks: str, k: int) -> int:\n",
    "        min_cnt = 2**1000000\n",
    "        cnt = 0\n",
    "        win = ''\n",
    "        for i in range(len(blocks)-k+1):\n",
    "            win = blocks[i:i+k]\n",
    "            cnt = win.count('W')\n",
    "            if cnt < min_cnt:\n",
    "                min_cnt = cnt\n",
    "        return min_cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRecolors(self, blocks: str, k: int) -> int:\n",
    "        n = len(blocks)\n",
    "        res = n\n",
    "        for i in range(n-k+1):\n",
    "            cnt = 0\n",
    "            for j in range(i, i+k):\n",
    "                if blocks[j] == 'W':\n",
    "                    cnt += 1\n",
    "            res = min(cnt, res)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def minimumRecolors(self, blocks: str, k: int) -> int:\n",
    "        minx=math.inf\n",
    "        for i in range(0,len(blocks)-k+1):\n",
    "            minx=min(minx,blocks[i:i+k].count('W'))  \n",
    "        return minx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRecolors(self, blocks: str, k: int) -> int:\n",
    "        ans = k\n",
    "        for i in range(len(blocks) - k + 1):\n",
    "            ans = min(ans, blocks[i:i+k].count('W'))\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
